This application makes reference to, incorporates the same herein, and claims all benefits accruing under 35 U.S.C xc2xa7119 from an application entitled An ATM Switch And A Method For Determining Buffer Threshold earlier filed in the Korean Industrial Property Office on Jun. 11, 1997, and there duly assigned Ser. No. 97-24144 by that Office.
1. Field of the Invention
The present invention for the ATM switch of Input Buffering type using the back-pressure signal, relates to a buffer threshold controller controlling the threshold per input port of switch element, using cell buffer occupancy information stored in the buffer pool of the switch element. More particularly, the present invention is intended to provide an ATM switch comprising the buffer threshold controller to improve the throughput of cells transmitted to the input port by changing the threshold dynamically at regular conversion time for cell time, wherein the threshold is the criterion to make occurrence of back-pressure signal according to the distribution of cells inputted to each input port and to provide a method for determining the buffer threshold.
2. Description of the Related Art
With the increasing needs for large transfer capacity and high speed transmission of digital data communication network systems, such as the broadband integrated services digital network (BISDN), the development of a more efficient data-transfer routing scheme for such network systems has been in demand. In recent years, as one of the BISDN systems satisfying the requirements, attention is paid to a specific digital data network system that employs a specific packet-oriented data-transfer mode which uses asynchronous time division multiplexing techniques, which is called the asynchronous transfer mode (ATM). ATM is a dedicated-connection switching technology that organizes digital data into 53 byte cells, or packets, and transmits them over a medium using digital signal technology. Individually, a cell is processed asynchronously relative to other related cells and is queued before being multiplexed over the line. Along with SONET (Synchronous Optical Network) and several other technologies, ATM is a key component of BISDN.
The details of the data transmission principles in the ATM communication network system have been described in several recommendations as published by the international telegraph and telephone consultative committee (CCITT).
More specifically, with the ATM network, the multiplexed information flow to be communicated between the sender and receiver terminals is organized into a plurality of cells of fixed size. In ATM switching facilities it is frequently necessary to switch data cells from several input lines to one and the same output line. This is one of the reasons why data cells are temporarily stored before, during, or after the switching process. The temporary storage may be in the form of several parallel queues. The queues are treated by a priority relationship known as priority classes, so that the data cells are served differently according to which queue they belong to.
An ATM switch distinguishes itself from a circuit switch in that it must reconfigure itself essentially every cell period. Furthermore, it must deal with a cell stream from each of its input ports wherein each cell may be destined for a different output port. This leads to contention among cells for output ports, since it is entirely possible for cells from two input ports to be destined for the same output port at the same time. This implies the need for storage somewhere in the switch so that all cells can eventually reach their intended output port.
In many architectures, contention that occurs for an output port means that some portion of the switch is idle while a cell waits, implying degradation in the throughput of the switch. Because of the statistical nature of the arrivals of cells at the input ports and of the destinations, there usually exists some probability of cell loss, which must be minimized. Finally, even if there is no cell loss, periods of considerable contention lead to large numbers of cells being instructed to wait somewhere in the storage media of the switch, implying long delays through the switch for some cells some of the time, leading to variations in transport delay or cell jitter. The following references, incorporated by reference, describe some known ATM system architectures: U.S. Pat. No. 5,367,520 to Robert R. Cordell entitled Method And System For Routing Cells In An ATM Switch; U.S. Pat. No. 5,440,547 to Hiroshi Easki et al. entitled Data-Transfer Routing Management For Packet-Oriented Digital Communication System Including ATM Networks; U.S. Pat. No. 5,453,980 to Robertus J. Van Engelshoven entitled Communication Network And Computer Network Server And INterface Modules Used Therein; U.S. Pat. No. 5,521,923 to Gert Willmann et al. entitled Method And Facility For Temporarily Storing Data Packets, And Exchange With Such Facility; U.S. Pat. No. 5,530,806 to Joseph H. Condon et al. entitled Method And Apparatus For Storing And Retrieving Routing Information In A Network Node; U.S. Pat. No. 5,570,348 to Brian D. Holden entitled Method And Apparatus For Enqueueing Data Cells In An ATM Switch Fabric Architecture; U.S. Pat. No. 5,583,861 to Brian D. Holden entitled ATM Switching Element And Method Having Independently Accessible Cell Memories; and U.S. Pat. No. 5,704,047 to Stefan Schneeberger entitled ATM Communication System Wherein Upstream Switching Element Stops The Transmission Of Message For A Predetermined Period Of Time Upon Backpressure Signal.
In view of the foregoing references, a simple ATM switch can be constructed by preceding a crosspoint array with a FIFO (first-in-first-out) input buffer on each of its input ports. A contention resolution device then examines all of the output port requests, comparing them against one another, and decides which FIFOs may empty a cell into the switch core, permitting only one cell to be routed to any given output port. Cells that contend and lose will get a chance to leave their FIFO during the next cell period. If none of these input buffers overflows, then there will be no cell loss. A losing contender at the head of one of these queues or lines forces all cells behind it to wait, even if they are destined for an output port that is free.
This type of architecture is called an input buffered switch. A system architecture of an Nxc3x97N input buffer switching system using a method of input buffering includes a routing table element attaching a routing tag to an ATM input cell using the information of the output port, an input buffer storing the cells being input and a switching fabric having a cell-transmission function between an input port and an output port using the routing tag. A routing table element and an input buffer are required, at a one to one relationship, for every input port and the switching fabric may be comprised of a unit switch or several unit switches.
The cells being input to the switching system, above all, are sent to routing table element, and the routing table element directs the storage of the input cell to the appropriate logical queue within the input buffer according to the class of the input cell. In the switch system, the input buffer is split into a plurality of logical queues to support a plurality of priorities.
The method for transmitting a cell in the logical queues to the routing table element is such that the method checks first in the logical queues if a cell is stored from the logical queue having the highest priority one after another. If there is a cell to be transmitted in the logical queue that has been checked, it checks if there is a back-pressure signal corresponding to the checked logical queue.
The switch fabric has a table that stores the priority of the cell, which is in the shared buffer, and the number of each of the priority cells for each input port. If the cells having the same priorities are transmitted to the same input ports, a collision may happen between the cells having the same priorities and the same input ports. So, a back-pressure signal is used to prevent such a collision.
In a case where the back-pressure signal does not exist, the cell is read from the input buffer and transmitted to the switch fabric through the routing table element. And in a case where the back-pressure signal exists, the method checks if there is a cell that is stored for the logical queue of the next priority and if there is a back-pressure signal corresponding to the logical queue. Namely, the method checks if there is a cell in the logical queue, and if there is not a back-pressure signal, transmits the cell through the switch fabric. Until an input cell is read from the input buffer, the method checks the logical queues and transmits the cell through the input port.
The static allocation for logical queue size has a disadvantage in that it can not accept variations in the dynamic traffic, smoothly.
For example, in case where the cells having a number of priorities are input with equal distribution and the same depths are allocated for each priority buffer, if a large number of cells with a specific priority are input, then empty areas may occur in the logical queues having other priorities and a large number of cell losses occur in the logical queues having the specific priorities are input as the buffers are insufficient.
Namely, in the prior method, the input buffer depth has a fixed allocation area statically. Therefore, if the input traffics are changed quite a bit, compared with the input traffics when the depth of the input buffer is defined, a relatively large cell loss may occur.
A known ATM switching system architecture of a switch fabric-type is built of a plurality of ATM switch element circuits and routing table circuits for each physical connection to/from the switch fabric. A shared pool of memory is employed to eliminate the need to provide memory at every crosspoint.
The back-pressure signal is sent to the routing table through the corresponding input port when the number of the cells included in the class of the specific priority, which are transmitted to the specific input port, is greater than a predetermined threshold per priority, and when the number of all cells stored in the unit switch is greater than the total threshold. For example, in case where the predetermined threshold is 2 and total threshold of the buffer pool is 24, if the number of cells included in the specific priority class in the buffer pool of the unit switch element is up to 2 or more, the back-pressure signal is transmitted so as to prevent the specific priority cell from being transmitted only to the corresponding input port and if total number of cells in the buffer pool is up to 24 or more, the back-pressure signals are transmitted to all input ports.
In the conventional way, the back-pressure signal has been generated using the threshold of the same classes for all input ports of the switching element. When the distribution of the cells input to each input port is same, it is called a uniform traffic environment. In this environment, the drop in throughput of the switching system does not occur in the conventional way, but in the practical environments, a case such that the cells are clustered to the specific port of the input port rather than the uniform traffic may occur. It is called a non-uniform traffic environment or hot-spot. In this case, although there is a receiving capacity of cells in the buffer pool, the back-pressure signals for the cells are transmitted to the input port side when a large number of cells are input to the specific input port, so more cells can not be transmitted and the throughput of the switching system becomes low.
As stated above, in the practical ATM switching system, the distribution of the cell inputted is generally not uniform traffic environment but hot-spot traffic environment. When using the conventional method of determining the threshold in such a ATM switching system, the back-pressure signal of the cell inputted to the specific input port occurs frequently, so the drop in throughput of cells is indispensable in general.
The present invention is intended to solve the problem as stated above and the invention has an object to provide an ATM switch comprising a buffer threshold controller to improve the throughput of cells from the non-uniform input traffics by dynamically allocating the threshold for each port at regular time intervals using the storage information of cells per input port for the cells stored in the switch and using the threshold information determined per input port and to provide a method for determining the buffer threshold.
The other object of the present invention is to improve the cell throughput by dynamically changing the threshold of each input port at regular cell time of conversion time interval, W, using the storage information of cells stored in the buffer pool per input port in the ATM switching system.
The present invention discloses an ATM switch comprising the buffer threshold controller to control the cell input into the switching element using the back-pressure signal and a method for determining the buffer threshold.
The ATM switch includes buffer pool storing the cell input to the switch; buffer pool control part storing the buffer pool occupancy information per input port of the buffer pool; threshold control part receiving the buffer pool occupancy information from the buffer pool control part and calculating the threshold per input port periodically and then sending it to the buffer pool control part; input crosspoint control part controlling the cells input to the buffer pool by receiving the control signal from the buffer pool control part; and output crosspoint control part controlling the cells being output from the buffer pool by receiving the control signal from the buffer pool control part.
According to one embodiment of the present invention, it is preferable that the ATM switch improves the throughput in the way that calculates the threshold based on an algorithm for determining the threshold size by using the buffer pool occupancy information sent from the buffer pool control part and makes the back-pressure signal by sending the calculated threshold size signal to the buffer pool control part.
And the present invention discloses a method for determining the buffer threshold size in the buffer threshold controller of the ATM switch that controls the cell input to the switching element using the back-pressure signal.
Other objects and advantages of the invention will become apparent upon reading the following detailed descriptions and upon reference to the drawing.